package com.linchong.dynamicprogramming.hard;

import java.awt.*;

/**
 * @author linchong
 * @version 1.0
 * @Date: 2020-11-19 8:56
 * @Description: PaintHouseII$265-粉刷房子II-https://leetcode-cn.com/problems/paint-house-ii/
 */
public class PaintHouseII {


	/**
	 * 序列型动态规划
	 * 假如有一排房子，共 n 个，每个房子可以被粉刷成 k 种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。
	 * <p>
	 * 当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x k 的矩阵来表示的。
	 * <p>
	 * 例如，costs[0][0] 表示第 0 号房子粉刷成 0 号颜色的成本花费；costs[1][2] 表示第 1 号房子粉刷成 2 号颜色的成本花费，以此类推。请你计算出粉刷完所有房子最少的花费成本。
	 * <p>
	 * 注意：
	 * <p>
	 * 所有花费均为正整数。
	 * <p>
	 * 来源：力扣（LeetCode）
	 * 链接：https://leetcode-cn.com/problems/paint-house-ii
	 * <p>
	 * 示例：
	 * <p>
	 * 输入: [[1,5,3],[2,9,4]]
	 * 输出: 5
	 * 解释: 将 0 号房子粉刷成 0 号颜色，1 号房子粉刷成 2 号颜色。最少花费: 1 + 4 = 5;
	 *      或者将 0 号房子粉刷成 2 号颜色，1 号房子粉刷成 0 号颜色。最少花费: 3 + 2 = 5.
	 * <p>
	 * <p>
	 * step 1:确定状态
	 * 最后一步：房子n-1的花费是最小的，同时还要保证相邻的房子不重复颜色，即房子n-1是k中颜色中的一种且花费最小，所以有，
	 * 子问题：
	 * 粉刷前n房子的花费 -> min(粉刷前n-1栋房子的花费且第n-2栋房子是某一种特定颜色+粉刷房子n-1且颜色是某种特定颜色的花费)
	 * <p>
	 * <p>
	 * <p>
	 * step 2:状态转移方程
	 * f[n][k] = min(f[n-1][i],f[n-1][j],f[n-1][l]...)+cost[n-1][k],其中[i!=k,j!=k,...]
	 * <p>
	 * step 3:初始值和边界情况
	 * f[0][0]=f[0][1]=...=f[0][k]=0
	 * <p>
	 * <p>
	 * step 4:计算顺序
	 * f[0][0]+f[0][1]+...+f[0][k]
	 * f[1][0]+f[1][1]+...+f[1][k]
	 * ...
	 * f[n-1][0]+f[n-1][1]+...+f[n-1][k]
	 * <p>
	 * 优化：
	 * f[i][j] = min(k!=j){f[i-1][k]}+cost[i-1][j]
	 * <p>
	 * 内循环k*k,即确定房子i和颜色后，每次还要求f[i-1][1],...,f[i-1][k]中除了一个元素（非重复颜色）之外的其他颜色的最小值
	 * <p>
	 * 假设最小的元素时第i个元素，次小值是第j个元素
	 * 1.只要除掉的元素不是第i个元素，剩下的最小值就是第i个元素
	 * 2.如果除掉的元素是第i个元素，剩下的最小值就是第j个元素
	 * 综上，不需要遍历，最小值就在i和j之间得到
	 * <p>
	 * 记录下f[i-1][1],...,f[i-1][k]中的最小值和次小值分别是那个
	 * <p>
	 * 假如最小值是f[i-1][a],次小值是f[i-1][b]
	 * 则对于非a颜色的j颜色j=1,2,3,...,a,a+1,...k，有f[i][j] = f[i-1][a]+cost[i-1][j]
	 * <p>
	 * 只有当j=a时，
	 * f[i][j] = f[i-1][b]+cost[i-1][j]
	 */
	public int minCostII(int[][] costs) {

		if (costs == null || costs.length == 0) {
			return 0;
		}

		int n = costs.length;

		int k = costs[0].length;

		if (k == 1) {
			return costs[0][0];
		}

		// 注意，n栋房子 0...n
		int[][] f = new int[n + 1][k];

		// init
		for (int i = 0; i < k; i++) {
			f[0][i] = 0;
		}


		for (int i = 1; i <= n; i++) {
			// 粉刷最后一个房子的花费
			for (int j = 0; j < k; j++) {
				// 粉刷前i房子的最小花费
				f[i][j] = Integer.MAX_VALUE;
				for (int l = 0; l < k; l++) {
					//房子颜色相同
					if (j == l) {
						continue;
					}
					// 更新最小花费
					if (f[i - 1][l] + costs[i - 1][j] < f[i][j]) {
						f[i][j] = f[i - 1][l] + costs[i - 1][j];
					}
				}
			}

		}
		int res = Integer.MAX_VALUE;
		for (int i = 0; i < k; i++) {
			if (res > f[n][i]) {
				res = f[n][i];
			}
		}
		return res;
	}

	/**
	 * 优化时间复杂度O(NK)
	 * 确定了房子i和颜色j后，每次还要从f[i-1][1],f[i-1][2],...,f[i-1][k]找颜色不重复最小值
	 *
	 * @param costs
	 * @return
	 */
	public int minCostIIP(int[][] costs) {

		if (costs == null || costs.length == 0) {
			return 0;
		}

		int n = costs.length;
		int k = costs[0].length;

		// 前n栋房子，0...n
		int[][] f = new int[n+1][k];

		// init
		for (int i = 0; i < k; i++) {
			f[0][i] = 0;
		}

		// 最小值和次小值
		int min1,min2;
		// 最小值位置，次小值位置
		int j1=0,j2=0;

		for (int i = 1; i <= n; i++) {
			// 确定房子i和颜色j后，每次都要在0~(i-1)中选一个不重复的最小值，优化它，提前存储最小值和次小值，根据情况判断是用最小值还是次小值
			//每次维护一个最小值和次小值
			min1 = min2 = Integer.MAX_VALUE;
			for (int j = 0; j < k; j++) {
				// 小于最小值
				if(f[i-1][j]<min1){
					min2 = min1;
					j2 = j1;
					min1 = f[i-1][j];
					j1 = j;
				}else{
					if(f[i-1][j]<min2){
						min2 = f[i-1][j];
						j2 = j;
					}
				}
			}

			// 求最小值f[i][j]
			for (int j = 0; j < k; j++) {
				if(j!=j1){
					f[i][j] = f[i-1][j1]+costs[i-1][j];
				}else{
					f[i][j] = f[i-1][j2]+costs[i-1][j];
				}
			}
		}


		int res = Integer.MAX_VALUE;
		for (int i = 0; i < k; i++) {
			res = Math.min(res,f[n][i]);
		}
		return res;
	}

	public static void main(String[] args) {
		int[][] costs = {{8}};
		PaintHouseII instance = new PaintHouseII();
		// 时间复杂度O(nk^2)
		System.out.println(instance.minCostII(costs));

		System.out.println(instance.minCostIIP(costs));
	}
}
